#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#include <string.h>

// 节点
typedef struct treenode
{
    int data;
    struct treenode *lchild;
    struct treenode *rchild;
}treenode, *linktree;

#define TREENODE treenode
#include "drawtree.h"

#define QUEUE_DATATYPE linktree
#include "linkqueue.h"

// 二叉搜索树的节点添加
linktree add_node(linktree root, treenode *new)
{
    // 一定可以直接返回的条件
    if(root == NULL)
        return new; // 直接将新节点作为树的根节点

    if(new->data < root->data)
        root->lchild = add_node(root->lchild, new);
    else if(new->data > root->data)
        root->rchild = add_node(root->rchild, new);
    else
    {
        printf("不允许重复的节点！\n");
        return root;
    }

    return root;
}

treenode *new_treenode(int data)
{
    treenode *new = calloc(1, sizeof(treenode));
    if(new != NULL)
    {
        new->data = data;
        new->lchild = NULL;
        new->rchild = NULL;
    }
    return new;
}

void pre_order(linktree root)
{
    if(root == NULL)
        return;
    printf("%d\t", root->data); // 访问根节点
    pre_order(root->lchild);    // 访问左子树
    pre_order(root->rchild);    // 访问右子树
}
void mid_order(linktree root)
{
    if(root == NULL)
        return;
    mid_order(root->lchild);
    printf("%d\t", root->data); // 访问根节点
    mid_order(root->rchild);
}
void pos_order(linktree root)
{
    if(root == NULL)
        return;
    pos_order(root->lchild);
    pos_order(root->rchild);
    printf("%d\t", root->data); // 访问根节点
}

// 功能：给我一棵二叉树的根指针，以及你要删除的数据
//       给你删除掉对应的节点，并返回新的根指针
linktree del_node(linktree root, int n)
{
    if(n < root->data)
        root->lchild = del_node(root->lchild, n);
    else if(n > root->data)
        root->rchild = del_node(root->rchild, n);
    else
    {
        // 1. 有左子树
        if(root->lchild)
        {
            linktree p;
            for (p = root->lchild; p->rchild != NULL; p = p->rchild);
            root->data = p->data; // 用左子树中最大（p指向左子树中最右下角的节点）的顶替root
            root->lchild = del_node(root->lchild, p->data);
        }
        // 2. 有右子树
        else if(root->rchild)
        {
            linktree p;
            for (p = root->rchild; p->lchild != NULL; p = p->lchild);
            root->data = p->data;// 用右子树中最小（p指向右子树中最左下角的节点）的顶替root
            root->rchild = del_node(root->rchild, p->data);
        }
        // 3. root是光杆司令
        else
        {
            free(root);
            return NULL;
        }
    }
    return root;
}

int main(int argc, char const *argv[])
{
    // 构建一棵BST
    linktree root = NULL;

    int n;
    while(1)
    {
        scanf("%d", &n);

        if(n > 0)
        {
            treenode *new = new_treenode(n);
            root = add_node(root, new);
        }
        else if(n < 0)
        {
            root = del_node(root, -n);
        }
        if(n == 0)
            break;

        draw(root); // 生成HTML文件
    }


    // 前中后序遍历：
    pre_order(root); printf("\n");
    mid_order(root); printf("\n");
    pos_order(root); printf("\n");

    // 按层遍历：
    queue *q = init_queue();
    en_queue(q, new_node(root));

    while(!is_empty(q))
    {
        list k;
        out_queue(q, &k);
        printf("%d\t", k->data->data); // int

        if(k->data->lchild)
            en_queue(q, new_node(k->data->lchild));
        if(k->data->rchild)
            en_queue(q, new_node(k->data->rchild));
    }

    return 0;
}
